package btree;

import java.io.DataOutputStream;
import java.io.FileOutputStream;
import java.io.IOException;

import exceptions.KeyNotMatchException;
import exceptions.KeyTooLongException;

import exceptions.UnpinPageException;

import exceptions.*;
import diskmgr.DiskMgrException;
import diskmgr.DuplicateEntryException;
import diskmgr.FileIOException;
import diskmgr.FileNameTooLongException;
import diskmgr.InvalidPageNumberException;
import diskmgr.InvalidRunSizeException;
import diskmgr.OutOfSpaceException;
import diskmgr.Page;
import exceptions.PinPageException;
import global.AttrType;
import global.GlobalConst;
import global.PageId;
import global.RID;
import global.SystemDefs;
import heap.HFPage;

public class BTreeFile extends IndexFile implements GlobalConst {

	public static BTreeHeaderPage headerPage;
	private PageId root;
public static PageId headerPageId;
private static FileOutputStream fos;
public static DataOutputStream trace;
public final static String lineSep = System.getProperty("line.separator"); 
public BTreeFile(String fileName) throws ConstructPageException,
			FileIOException, InvalidPageNumberException, DiskMgrException,
			IOException {

		PageId pid = SystemDefs.JavabaseDB.get_file_entry(fileName);
		headerPage = new BTreeHeaderPage(pid);
		headerPageId=pid;
		root = headerPage.getRoot();

	}

	public BTreeFile(String filename, int keytype, int keysize,
			int delete_fashion) throws ConstructPageException {

		try {
			headerPageId = SystemDefs.JavabaseDB.get_file_entry(filename);
		} catch (FileIOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (InvalidPageNumberException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (DiskMgrException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		if (headerPageId == null) // file not exist
		{
			headerPage = new BTreeHeaderPage();
			try {
				headerPageId = headerPage.getCurPage();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			try {
				SystemDefs.JavabaseDB.add_file_entry(filename, headerPageId);
			} catch (FileNameTooLongException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} catch (InvalidPageNumberException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} catch (InvalidRunSizeException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} catch (DuplicateEntryException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} catch (OutOfSpaceException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} catch (FileIOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} catch (DiskMgrException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
//			headerPage.set_magic0(MAGIC0);
			headerPage.setRoot(new PageId(INVALID_PAGE));
			headerPage.setKeyType((short) keytype);
//			headerPage.set_maxKeySize(keysize);
//			headerPage.set_deleteFashion(delete_fashion);
			try {
				headerPage.setType(NodeType.BTHEAD);
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		} else {
			headerPage = new BTreeHeaderPage(headerPageId);
		}

		// try {
		//
		//
		// } catch (IOException e) {
		// // TODO Auto-generated catch block
		// e.printStackTrace();
		// }

	}
	public static void traceFilename(String filename) throws IOException {

		fos = new FileOutputStream(filename);
		trace = new DataOutputStream(fos);
	}
	@Override
	public boolean Delete(KeyClass key, RID rid) throws btree.KeyNotMatchException {
		try {
			return NaiveDelete(key, rid);
		} catch (LeafDeleteException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (KeyNotMatchException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (PinPageException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (ConstructPageException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (UnpinPageException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IndexSearchException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IteratorException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return false;
	}


	private void updateHeader(PageId newRoot) throws IOException,
			PinPageException, UnpinPageException {

		BTreeHeaderPage header;

		header = new BTreeHeaderPage(pinPage(headerPageId));

		headerPage.getRoot();
		header.setRoot(newRoot);

		// clock in dirty bit to bm so our dtor needn't have to worry about it
		unpinPage(headerPageId, true /* = DIRTY */);

		// ASSERTIONS:
		// - headerPage, headerPageId valid, pinned and marked as dirty

	}

	@Override
	public void insert(KeyClass data, RID rid) throws btree.KeyNotMatchException, KeyTooLongException, IOException, KeyNotMatchException {
		// TODO Auto-generated method stub
		if (BT.getKeyLength(data) > headerPage.getKeySize())
			throw new KeyTooLongException(null, "");
		if (data instanceof StringKey) {
			if (headerPage.getKeyType() != AttrType.attrString) {
				throw new KeyNotMatchException(null, "");
			}
		} else if (data instanceof IntegerKey) {
			if (headerPage.getKeyType() != AttrType.attrInteger) {
				throw new KeyNotMatchException(null, "");
			}
		} else
			throw new KeyNotMatchException(null, "");
		if (trace != null) {
			try {
				trace.writeBytes("INSERT " + rid.pageNo + " " + rid.slotNo + " "
						+ data + lineSep);
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			try {
				trace.writeBytes("DO" + lineSep);
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			try {
				trace.flush();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
		if (headerPage.getRoot().pid == INVALID_PAGE) {
			PageId newRootPageId = null;
			BTLeafPage newRootPage = null;
			

			try {
				newRootPage = new BTLeafPage(headerPage.getKeyType());
			} catch (ConstructPageException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			try {
				newRootPageId = newRootPage.getCurPage();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			if (trace != null) {
				try {
					trace.writeBytes("NEWROOT " + newRootPageId + lineSep);
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
				try {
					trace.flush();
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			try {
				newRootPage.setNextPage(new PageId(INVALID_PAGE));
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			try {
				newRootPage.setPrevPage(new PageId(INVALID_PAGE));
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}

			// ASSERTIONS:
			// - newRootPage, newRootPageId valid and pinned

			try {
				newRootPage.insertRecord(data, rid);
			} catch (LeafInsertRecException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			if (trace != null) {
				try {
					trace.writeBytes("PUTIN node " + newRootPageId + lineSep);
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
				try {
					trace.flush();
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			try {
				unpinPage(newRootPageId);
			} catch (UnpinPageException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} /* = DIRTY */
			 try {
				updateHeader(newRootPageId);
			} catch (PinPageException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} catch (UnpinPageException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			if (trace != null) {
				try {
					trace.writeBytes("DONE" + lineSep);
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
				try {
					trace.flush();
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			return;
		} else {
			if (trace != null) {
				try {
					trace.writeBytes("SEARCH" + lineSep);
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
				try {
					trace.flush();
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			KeyDataEntry rootEntry = null;
			try {
				rootEntry = insertP(headerPage.getRoot(), data, rid);
			} catch (IteratorException e1) {
				// TODO Auto-generated catch block
				e1.printStackTrace();
			} catch (DeleteRecException e1) {
				// TODO Auto-generated catch block
				e1.printStackTrace();
			} catch (ConvertException e1) {
				// TODO Auto-generated catch block
				e1.printStackTrace();
			}
			if (rootEntry != null) {
				// the root is splitted
				// we need new root
				PageId newRootPageId;
				try {
					BTIndexPage newRoot = new BTIndexPage(
							headerPage.getKeyType());
					newRootPageId= newRoot.getCurPage();
					if (trace != null) {
						trace.writeBytes("NEWROOT " + newRootPageId+ lineSep);
						trace.flush();
					}
					newRoot.insertKey(rootEntry.key,
							((IndexData) rootEntry.data).getData());
					// the old root split and is now the left child of the new
					// root
					newRoot.setPrevPage(headerPage.getRoot());
					unpinPage(newRoot.getCurPage());
					//headerPage.setRoot(newRoot.getCurPage());
					try {
						updateHeader(newRoot.getCurPage());
					} catch (PinPageException e) {
						// TODO Auto-generated catch block
						e.printStackTrace();
					}
				} catch (ConstructPageException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				} catch (IndexInsertRecException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				} catch (UnpinPageException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}

			}
		}

		// lazm a7tfz b el root elly kol mara hbd2 mno

		// hst5dm el method bta3t getPageNoByKey

		// ageeb el page elly btshawer 3leeha el key da
		// a pin el page elly gbtha
		// lw el page elly gt kant index page yb2a ana lesa mwsltesh
		// a3ml nfs elly 3mlto tany l7d ma awsel l leaf page
		// insert el data fy el leaf
		// lw 7sl overflow h split
		// lazm arg3 tany up w at2kd lw m7taga a3ml split tany l indexPage
		// lw el root 7slo split hwa kman m7taga a7ot root gdeed w a5ly en hwa
		// da el root
		if (trace != null) {
			try {
				trace.writeBytes("DONE" + lineSep);
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
			try {
				trace.flush();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
	}

	private KeyDataEntry insertP(PageId currentPageId, KeyClass data, RID rid)
			throws IteratorException, DeleteRecException, ConvertException {
		BTSortedPage current;
		KeyDataEntry entry;
		Page page = new Page();
		try {
			page = pinPage(currentPageId);
		} catch (PinPageException e1) {
			// TODO Auto-generated catch block
			e1.printStackTrace();
		}
		short pageType;
		try {
			current = new BTSortedPage(page, headerPage.getKeyType());
			if (trace != null) {
				trace.writeBytes("VISIT node " + currentPageId + lineSep);
				trace.flush();
			}
			pageType = current.getType();
			if (pageType == NodeType.INDEX) {
				BTIndexPage currentIndex = (BTIndexPage) current;
				PageId currentIndexPageId = currentPageId;
				PageId nextId = currentIndex.getPageNoByKey(data);
				// BTSortedPage nextPage = new BTSortedPage(nextId,
				// headerPage.getKeyType());
				unpinPage(currentPageId);
				entry = insertP(nextId, data, rid);
				if (entry == null) {
					// no split occurs
					return null;
				}
				currentIndex = new BTIndexPage(currentIndexPageId,
						headerPage.getKeyType());
				
				if (currentIndex.available_space() >= BT.getKeyDataLength(data,
						NodeType.INDEX)) {
					currentIndex.insertKey(entry.key,
							((IndexData) entry.data).getData());
					unpinPage(currentIndexPageId);
					return null;
					// we are done
				} else {
					// split
					entry = currentIndex.split(entry,currentIndexPageId);
					// unpinPage(currentPageId);
					return entry;
				}

			} else {
				// leaf
				BTLeafPage leaf = (BTLeafPage) current;
				PageId currentLeafPageId = currentPageId;
				if (leaf.available_space() >= BT.getKeyDataLength(data,
						NodeType.LEAF)) {
					// no split
					leaf.insertRecord(data, rid);
					unpinPage(currentPageId);
					if (trace != null) {
						trace.writeBytes("PUTIN node " + currentLeafPageId
								+ lineSep);
						trace.flush();
					}
					return null;// indicates no split
					// we are done
				} else {
					// split
					KeyDataEntry currentEntry = leaf.split(data, rid,
							currentLeafPageId);
					KeyDataEntry parentEntry = new KeyDataEntry(
							currentEntry.key, leaf.getNextPage());
					return parentEntry;
				}
			}
		} catch (ConstructPageException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (NodeNotMatchException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (LeafInsertRecException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (UnpinPageException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IndexInsertRecException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (btree.KeyNotMatchException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return null;
	}

	// private void insertP(PageId pidParent, PageId pidChild, KeyClass data,
	// RID rid) {
	// boolean cantInsert = false;
	// try {
	//
	// BTSortedPage next = new BTSortedPage(pidChild,
	// headerPage.getKeyType());
	//
	// if (next.getType() == NodeType.INDEX) {
	//
	// BTIndexPage newParent = (BTIndexPage) next;
	// PageId newChildId = newParent.getPageNoByKey(data);
	// KeyDataEntry newEntry = new KeyDataEntry(data, rid);
	// if (newParent.available_space() < BT.getKeyDataLength(data,
	// newParent.getType())) {
	//
	// //newParent.split();
	// BTIndexPage oldParent = new
	// BTIndexPage(pidParent,headerPage.getKeyType());
	// PageId nextChildId = newParent.getNextPage();
	// BTIndexPage nextChild = new
	// BTIndexPage(nextChildId,headerPage.getKeyType());
	// RID newRid= new RID(nextChildId,0);
	// KeyDataEntry firstEntry = nextChild.getFirst(newRid);
	// KeyDataEntry newEntryP = new KeyDataEntry(firstEntry.key, nextChildId);
	// insertP(pidParent, nextChildId, data, newRid);
	// }
	// newParent.insertRecord(newEntry);
	// // BTSortedPage newChild = new BTSortedPage(newChildId,
	// // headerPage.getKeyType());
	// insertP(pidChild, newChildId, data, rid);
	// }
	// } catch (ConstructPageException e) {
	// // TODO Auto-generated catch block
	// e.printStackTrace();
	// } catch (IOException e) {
	// // TODO Auto-generated catch block
	// e.printStackTrace();
	// } catch (InsertRecException e) {
	// // TODO Auto-generated catch block
	// cantInsert = true;
	// e.printStackTrace();
	// } catch (KeyNotMatchException e) {
	// // TODO Auto-generated catch block
	// e.printStackTrace();
	// } catch (NodeNotMatchException e) {
	// // TODO Auto-generated catch block
	// e.printStackTrace();
	// } catch (IteratorException e) {
	// // TODO Auto-generated catch block
	// e.printStackTrace();
	// }
	//
	//
	// }
	//
	// private void insertP(PageId pidParent,PageId pidChild,KeyClass data,RID
	// rid)
	// {
	// try {
	// BTSortedPage next = new BTSortedPage(pidChild,headerPage.getKeyType());
	//
	// if(next.getType()==NodeType.INDEX){
	// BTIndexPage newParent = (BTIndexPage) next;
	// PageId newChildId = newParent.getPageNoByKey(data);
	// KeyDataEntry newEntry = new KeyDataEntry(data, rid);
	// newParent.insertRecord(newEntry);
	// //BTSortedPage newChild = new BTSortedPage(newChildId,
	// headerPage.getKeyType());
	// insertP(pidChild, newChildId, data,rid);
	//
	// }
	// } catch (ConstructPageException e) {
	// // TODO Auto-generated catch block
	// e.printStackTrace();
	// } catch (IOException e) {
	// // TODO Auto-generated catch block
	// e.printStackTrace();
	// } catch (InsertRecException e) {
	// // TODO Auto-generated catch block
	//
	// e.printStackTrace();
	// }
	// }

	public void close() {
		if (headerPage != null) {
			try {
				unpinPage(root, true);
			} catch (UnpinPageException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
		headerPage = null;
	}

	// done
	private void destroy(PageId currentPageId) {
		try {
			Page page = pinPage(currentPageId);
			BTSortedPage current = new BTSortedPage(page,
					headerPage.getKeyType());
			if (current.getType() == NodeType.LEAF) {
				unpinPage(currentPageId);
				freePage(currentPageId);
			} else {
				RID recored = new RID();
				BTIndexPage currentIndexPage = new BTIndexPage(page,
						headerPage.getKeyType());
				KeyDataEntry currentEntry = currentIndexPage.getFirst(recored);
				for (KeyDataEntry entry = currentEntry; entry != null; currentIndexPage
						.getNext(recored)) {
					PageId childId = ((IndexData) (entry.data)).getData();
					destroy(childId);
				}
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (PinPageException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IteratorException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (UnpinPageException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (FreePageException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

	// done
	public void destroyFile() {
		if (headerPage != null) {
			PageId pgId = headerPage.getRoot();
			BTSortedPage current;
			if (pgId.pid != INVALID_PAGE) {
				destroy(pgId);
			}

			try {
				unpinPage(headerPage.getRoot());
				freePage(headerPage.getRoot());
				delete_file_entry(headerPage.getFileName());
				headerPage = null;
			} catch (UnpinPageException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} catch (FreePageException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			} catch (DeleteFileEntryException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}

		}
	}

	// done
	public BTFileScan new_scan(KeyClass lo_key, KeyClass hi_key)
			throws UnpinPageException, PinPageException, IteratorException,
			KeyNotMatchException, IOException, btree.KeyNotMatchException {
		BTFileScan scan = new BTFileScan();
		// BTree is empty
		if (headerPage.getRoot().pid == INVALID_PAGE) {
			scan.leafPage = null;
			return scan;
		}
		//
		scan.setEndkey(hi_key);
		scan.setScanFirst(false);
		scan.setCurrentDeleted(false);
		scan.setCurRid(new RID());
		scan.setKeyType(headerPage.getKeyType());
		scan.setMaxKeysize(headerPage.getKeySize());
		scan.setBtree(this);

		// this sets up scan at the starting position, ready for iteration
		scan.leafPage = getFirstLeafPage(lo_key, scan.getCurRid());
		return scan;
	}

	

	BTLeafPage getFirstLeafPage(KeyClass lowKey, RID startrid)
			throws UnpinPageException, PinPageException, IteratorException,
			KeyNotMatchException, IOException, btree.KeyNotMatchException {

		PageId pageNo = headerPage.getRoot();

		// ------if root empty
		if (pageNo.pid == INVALID_PAGE) { // no pages in the BTREE
			return null;
		}

		// ------if root page is valid
		Page tempPage = pinPage(pageNo);

		// -----put in sorted page
		BTSortedPage tempSorted = new BTSortedPage(tempPage,
				headerPage.getKeyType());
		if (trace != null) {
			trace.writeBytes("VISIT node " + pageNo + lineSep);
			trace.flush();
		}
		// ----if tempSorted is index
		BTIndexPage indexPage;
		KeyDataEntry entry;
		PageId prevpageno;

		while (tempSorted.getType() == NodeType.INDEX) {
			// index page
			indexPage = new BTIndexPage(tempPage, headerPage.getKeyType());
			// previous page
			prevpageno = indexPage.getPrevPage();
			// first entry in index page
			entry = indexPage.getFirst(startrid);
			// get correct indexPage
			while (entry != null && lowKey != null
					&& BT.keyCompare(entry.key, lowKey) < 0) {

				prevpageno = ((IndexData) entry.data).getData();
				entry = indexPage.getNext(startrid);
			}
			// unpin page that i pinned it
			unpinPage(pageNo);

			pageNo = prevpageno;
			// page of the leafPage
			Page page = pinPage(pageNo);
			PageId nextpageno;
			if (trace != null) {
				trace.writeBytes("VISIT node " + pageNo + lineSep);
				trace.flush();
			}

			// ------------------------get proper leaf Page---------------------
			BTLeafPage pageLeaf = new BTLeafPage(page, headerPage.getKeyType());

			entry = pageLeaf.getFirst(startrid);

			// -------------if we have empty pages in first------------
			while (entry == null) {
				// get next
				nextpageno = pageLeaf.getNextPage();
				// upin page that i pinned it
				unpinPage(pageNo);
				if (nextpageno.pid == INVALID_PAGE) {
					// all records are empty
					return null;
				}

				pageNo = nextpageno;
				// get next page
				pageLeaf = new BTLeafPage(pinPage(pageNo),
						headerPage.getKeyType());
				// get first entry in the page
				entry = pageLeaf.getFirst(startrid);
			}
			// ----------------here i get leaf Page---------------------
			// -------------here check the key of the leaf page----------

			if (lowKey == null) {
				// return leaf page i get
				// still pinned "note!"
				return pageLeaf;
			}
			// get proper leaf page with low key
			while (BT.keyCompare(entry.key, lowKey) < 0) {
				// -----------------entry has key less than low key
				// given---------------
				// next entry
				entry = pageLeaf.getNext(startrid);
				while (entry == null) {
					// loop over leaf pages
					nextpageno = pageLeaf.getNextPage();
					unpinPage(pageNo);

					if (nextpageno.pid == INVALID_PAGE) {
						return null;
					}

					pageNo = nextpageno;
					pageLeaf = new BTLeafPage(pinPage(pageNo),
							headerPage.getKeyType());
					entry = pageLeaf.getFirst(startrid);
				}
				// page is already pinned
			}

			return pageLeaf;
		}
		return null;

	}
	// -------------------------------------------------------------------------------------
	public static Page pinPage(PageId pageno) throws PinPageException {
		try {
			Page page = new Page();
			SystemDefs.JavabaseBM.pinPage(pageno, page, false/* Rdisk */);
			return page;
		} catch (Exception e) {
			e.printStackTrace();
			throw new PinPageException(e, "");
		}
	}

	public static void unpinPage(PageId pageno) throws UnpinPageException {
		try {
			SystemDefs.JavabaseBM.unpinPage(pageno, true /* = not DIRTY */);
		} catch (Exception e) {
			e.printStackTrace();
			throw new UnpinPageException(e, "");
		}
	}

	private void freePage(PageId pageno) throws FreePageException {
		try {
			SystemDefs.JavabaseBM.freePage(pageno);
		} catch (Exception e) {
			e.printStackTrace();
			throw new FreePageException(e, "");
		}

	}

	private void delete_file_entry(String filename)
			throws DeleteFileEntryException {
		try {
			SystemDefs.JavabaseDB.delete_file_entry(filename);
		} catch (Exception e) {
			e.printStackTrace();
			throw new DeleteFileEntryException(e, "");
		}
	}

	private void unpinPage(PageId pageno, boolean dirty)
			throws UnpinPageException {
		try {
			SystemDefs.JavabaseBM.unpinPage(pageno, dirty);
		} catch (Exception e) {
			e.printStackTrace();
			throw new UnpinPageException(e, "");
		}
	}
	private boolean NaiveDelete(KeyClass key, RID rid)
			throws LeafDeleteException, KeyNotMatchException, PinPageException,
			ConstructPageException, IOException, UnpinPageException,
			PinPageException, IndexSearchException, IteratorException, btree.KeyNotMatchException {
		BTLeafPage leafPage;
		RID curRid = new RID(); // iterator
		PageId nextpage;
		KeyDataEntry entry;

		 if (trace != null) {
		 trace.writeBytes("DELETE " + rid.pageNo + " " + rid.slotNo + " "
		 + key + lineSep);
		 trace.writeBytes("DO" + lineSep);
		 trace.writeBytes("SEARCH" + lineSep);
		 trace.flush();
		 }

		leafPage = getFirstLeafPage(key, curRid); // find first page,rid of key
		if (leafPage == null)
			return false;

		entry = leafPage.getCurrent(curRid);

		while (true) {

			while (entry == null) { // have to go right
				nextpage = leafPage.getNextPage();
				unpinPage(leafPage.getCurPage());
				if (nextpage.pid == INVALID_PAGE) {
					return false;
				}

				leafPage = new BTLeafPage(pinPage(nextpage),
						headerPage.getKeyType());
				entry = leafPage.getFirst(new RID());
			}

			if (BT.keyCompare(key, entry.key) > 0)
				break;

			if (leafPage.delEntry(new KeyDataEntry(key, rid)) == true) {

				// successfully found <key, rid> on this page and deleted it.
				// unpin dirty page and return OK.
				unpinPage(leafPage.getCurPage(), true /* = DIRTY */);

				 if (trace != null) {
				 trace.writeBytes("TAKEFROM node " + leafPage.getCurPage()
				 + lineSep);
				 trace.writeBytes("DONE" + lineSep);
				 trace.flush();
				 }

				return true;
			}

			nextpage = leafPage.getNextPage();
			unpinPage(leafPage.getCurPage());

			leafPage = new BTLeafPage(pinPage(nextpage),
					headerPage.getKeyType());

			entry = leafPage.getFirst(curRid);
		}

		/*
		 * We reached a page with first key > `key', so return an error. We
		 * should have got true back from delUserRid above. Apparently the
		 * specified <key,rid> data entry does not exist.
		 */

		unpinPage(leafPage.getCurPage());
		return false;
	}

}
